import sun.reflect.generics.tree.Tree;

import java.util.ArrayList;
import java.util.List;

/**
 * Created whit IntelliJ IDEA.
 * Description：
 * User：ZHONGCHEN
 * Date:2022-07-25
 * Time:17:33
 */
//class TreeNode {
//    int val;
//    TreeNode left;
//    TreeNode right;
//
//    TreeNode() {
//    }
//
//    TreeNode(int val) {
//        this.val = val;
//    }
//
//    TreeNode(int val, TreeNode left, TreeNode right) {
//        this.val = val;
//        this.left = left;
//        this.right = right;
//    }
//}

/**
 * 919. 完全二叉树插入器--广度优先 bfs
 */
public class CBTInserter {
    int index = 0;
    List<TreeNode> list = new ArrayList<>();

    public CBTInserter(TreeNode root) {
        list.add(root);
        int cur = 0;
        while (cur < list.size()) {
            TreeNode node = list.get(cur);
            if (node.left != null) {
                list.add(node.left);
            }
            if (node.right != null) {
                list.add(node.right);
            }
            cur++;
        }
    }

    public int insert(int val) {
        TreeNode treeNode = new TreeNode(val);
        while (list.get(index).left != null && list.get(index).right != null) {
            index++;
        }
        TreeNode father = list.get(index);
        if (father.left == null) {
            father.left = treeNode;
        } else if (father.right == null) {
            father.right = treeNode;
        }
        list.add(treeNode);
        return father.val;
    }

    public TreeNode get_root() {
        return list.get(0);
    }
}
